package com.zhn;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 */

public class IsValidBST {
    //只需要中序遍历后，判断返回的结果集是否为递增序列
    List<Integer> res = new ArrayList<Integer>();
    public boolean isValidBST(TreeNode root) {
        travel(root,res);
        for(int i = 1;i < res.size(); i++){
            //节点值如果全相等也返回false
            if(res.get(i-1) >= res.get(i))
                return false;
        }
        return true;
    }
    //递归中序遍历
    public void travel(TreeNode root, List<Integer> results){
        if(root == null) {
            return;
        }
        travel(root.left,results);
        results.add(root.val);
        travel(root.right,results);
    }
}
